package seqlist.leetcode;

/**
 * 删除所有排序链表中的节点，重复节点都不保留
 *
 * @author yuisama
 * @date 2022/04/21 21:38
 **/
public class Num82_DeleteDuplicates {
        public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;
        while (cur != null) {
            ListNode next = cur.next;
            if (next == null) {
                // 当前链表只有一个节点，不可能重复
                // next走到null，所有节点判断完毕
                break;
            }else {
                // 此时链表至少存在两个有效节点
                // 不重复
                if (cur.val != next.val) {
                    // 三指针后移
                    cur = cur.next;
                    prev = prev.next;
                }else {
                    // 此时碰到重复元素，一直移动next指针
                    while (next != null && cur.val == next.val) {
                        next = next.next;
                    }
                    // next指向第一个不重复元素
                    // prev之后，next之前全是重复元素
                    prev.next = next;
                    cur = next;
                }
            }
        }
        return dummyHead.next;
    }

    /**
     * 传入一个链表的头节点，就能删除当前链表中所有重复节点，返回删除后的头节点
     * @param head
     * @return
     */
//    public ListNode deleteDuplicates(ListNode head) {
//        // 1.边界
//        if (head == null || head.next == null) {
//            return head;
//        }
//        // 2.判断头节点是否是待删除的节点
//        if (head.val != head.next.val) {
//            head.next = deleteDuplicates(head.next);
//            return head;
//        }else {
//            // 先处理头节点
//            ListNode nextHead = head.next;
//            while (nextHead != null && head.val == nextHead.val) {
//                nextHead = nextHead.next;
//            }
//            // nextHead一定是不重复的新的头节点
//            // 以当前新的头节点为链表的节点删除交给子函数
//            return deleteDuplicates(nextHead);
//        }
//    }
}